%include "asm_io.inc"

segment .data
;
;initialized data is put in the data segment here
;

prompt1 db "Number of elements:	",0	;initialize the messages
prompt2 db "Please give number ",0
prompt3 db ": ",0
prompt4 db "Please choose (1) Bubblesort, (2) Quicksort: "

outmsg1	db 10,0				;ascii for newline
outmsg2	db "The total number of swaps = ",0

debug1	db	"Debug 1",0
debug2	db	"Debug 2",0

numswaps dd 0

segment .bss
;
;uninitialized data is put in the bss segment
;

n resd 1			;reserve the number of elements variable
array resd 1000		;reserve space for 1000 numbers

holder1 resd 1
holder2 resd 1

currentSpot resd 1
nextSpot resd 1

segment .text
;
;code here
;

	global asm_main

asm_main:
	enter 0,0		;setup routine
	pusha

	mov eax, prompt1	;prepare 1st prompt
	call print_string	;print out 1st prompt

	call read_int		;read integer
	mov [n], eax		;store integer
	
	mov ecx,[n]			;sets the loop counter
	mov ebx, array		;store the beginnig of the array
	mov edx, 1			;store the index number
	
read_in:
	mov eax, prompt2	;prepare prompt for next value
	call print_string	;prints the prompt
	mov eax, edx		;prepares the number of prompt
	call print_int		;prints the number of the prompt
	mov eax, prompt3	;prepares the colon
	call print_string	;prints the colon
	
	call read_int		;read in the number
	mov [ebx], eax		;stores the number
	
	add ebx,4			;increments the location
	add edx,1			;increments the index
	loop read_in
	
	push array			;put array on stack
	push dword 0		;put initial index
	mov eax, [n]		;store n
	sub eax,1			;n-1
	push eax			;store n-1
	
	mov eax, prompt4	;prepare the choice prompt
	call print_string	;print the prompt
	call read_int		;read the response
	cmp eax, 1			;compare method selection to 1
	je bubble_call		;do the appropiate action
quick_call:	
	call quick_sort
	jmp end_call
bubble_call:
	call bubble_sort
end_call:	

	mov ecx,[n]			;sets the loop counter
	mov ebx, array		;store the beginnig of the array
	mov edx, 1			;store the index number
	
	mov eax, outmsg1	;newline
	call print_string	;print it
	
read_out:
	mov eax, [ebx]		;get the element
	call print_int		;print it out
	mov eax, outmsg1	;newline
	call print_string	;print it
	
	add ebx, 4			;increment counter
	loop read_out
	
	mov eax, outmsg2	;swaps
	call print_string	;print it
	mov eax, [numswaps]	;number swaps
	call print_int		;print it
	mov eax, outmsg1	;newline
	call print_string	;print it
	
	
	;cleanup code
	pop eax
	pop eax
	pop eax
	
	;do not remove code after this
	popa
	mov eax,0	;return back to C
	leave
	ret


;SIGNED BUBBLESORT GOES HERE 
;BLEGGGGHHHH
segment .text
	global bubble_sort

bubble_sort:
	enter 0,0	;enters
	pushad		;pushes all registers
	
	;ebx,ecx - the two numbers
	;edx - the local flip count
	;eax - the current index

while1:
	mov edx, 0			;start with 0
	
	mov ecx, [ebp+8]	;store the last index
	sub ecx, [ebp+12]	;subtract the first index, giving us the number of loops
	
	for1:
		mov eax, ecx		;store current index
		shl eax, 2			;multiply index by 4
		add eax, [ebp+16]	;add the base address
		add eax, [ebp+12]	;add the offset
		mov [holder1], eax	;save this address
		mov eax, [eax]		;get the value
		
		mov ebx, ecx		;store current index
		sub ebx, 1			;subtract 1
		shl ebx, 2			;multiply index by 4
		add ebx, [ebp+16]	;add the base address
		add ebx, [ebp+12]	;add the offset
		mov [holder2], ebx	;save this address
		mov ebx, [ebx]		;get the value
		
		cmp eax, ebx		;check if the values are different
		jge next_for		;check if we need to swap
			
			push ecx			;saving some registers temporarily
			push edx			;makin some room
			
			mov ecx, [holder1]	;gets address1
			mov edx, [holder2] 	;gets address2
			
			mov [ecx], ebx		;flip
			mov [edx], eax
			
			pop edx			;restores registers
			pop ecx
			
			add edx, 1			;increments edx
			
		next_for:
		loop for1
	
	add [numswaps], edx	;adds the number of swaps to the global swaps
	cmp edx,0			;compare our flip count
	jne while1			;if we haven't flipped, do more looping
	
	popad
	leave
	ret
	
;QUICKSORT GOES HERE I GUESS, WHY IS THIS SOOO CRUEL???
segment .text
	global quick_sort

quick_sort:	
	enter 0,0			;enters
	pushad				;pushes all registers
	
	mov eax,[ebp+8]		;stores last index
	mov ebx,[ebp+12]	;stores first index
	
	cmp eax,ebx			;compares last and first indices
	jg do_it			;check if we should stop
		popad				;puts back registers
		leave	
		ret
do_it:	
	add eax, ebx		;left+right
	shr eax, 1			;pivotindex = (left+right)/2

	push eax			;keep original pivot index for later		

	mov ecx, eax		;copy eax
	shl ecx, 2			;eax*4
	add ecx, [ebp+16]	;base address + index
	
	mov edx, [ebp+8]	;last index
	shl edx, 2			;last*4
	add edx, [ebp+16]	;base + index
	
	;doing swap array[index] with array[end]
	mov ebx, [ecx]		;get 1st value
	push ebx			;save pivotValue for later
	xchg [edx], ebx		;exchange values, store 1st
	mov [ecx], ebx		;store 2nd value
	
	add dword [numswaps], 1	;we did a swap
	
	pop ecx
	mov ebx,[ebp+12]	;stores first index, storeIndex
	mov eax,ebx			;stores index counter
	
	cmp eax, [ebp+8]	;see if we do the loop at all
	jg end_loop			;don't do it if we can't
int_loop:
	mov edx, eax		;computing address
	shl edx,2			;index*4
	add edx,[ebp+16]	;address
	
	cmp [edx], ecx		;array[i]<pivotValue?
	jge int_if_end
	
		push ecx		;save our pivotValue
		push ebx		;save our current index
		
		shl ebx,2		;storeIndex*2
		add ebx,[ebp+16];address
		
		mov ecx,[edx]	;swapping array[i] and array[storeindex]
		xchg ecx,[ebx]	;do the exchange
		mov [edx],ecx	;swapped
	
		pop ebx			;restore our current storeindex
		pop ecx			;restore our pivotValue
		
		add dword [numswaps], 1	;we did a swap
		add ebx, 1				;storeIndex+1
int_if_end:	
	add eax,1			;increment counter	
	cmp eax, [ebp+8]	;compares last index
	jl int_loop
end_loop:
	push ebx			;save ebx for later
	
	shl ebx,2			;address calc
	add ebx,[ebp+16]
	
	mov ecx, [ebp+8]	;put last index in the register
	shl ecx,2			;address calc
	add ecx,[ebp+16]
	
	mov edx, [ebx]		;swap
	xchg [ecx],edx
	mov [ebx], edx
	
	add dword [numswaps], 1	;we did a swap
	
	pop ebx				;restore ebx to storeIndex
	pop eax				;restore pivot index
	
	mov ecx, [ebp+16]	;array argument
	push ecx			;put on stack
	
	mov ecx, [ebp+12]	;left
	push ecx			;on stack
	
	mov ecx,ebx			;storeIndex
	sub ecx,1			;storeIndex-1
	push ecx
	
	call quick_sort
	pop ecx
	pop ecx
	
	mov ecx,ebx
	add ecx,1
	push ecx
	
	mov ecx,[ebp+8]
	push ecx
	
	call quick_sort
	pop ecx
	pop ecx
	pop ecx
	
quick_end:	
	popad				;puts back registers
	leave	
	ret
	